package project2;

/*
* 2019-11-21 插入排序
* 第一个元素是有序的，从第二个元素开始，逐个插入到之前的有序数组中
* 需要注意的是j的赋值和逐个元素后移的操作边界
* 这里默认排为升序
* */
public class Insertion {
    public void sort(int[] a){
        int n = a.length;
        for(int i = 1; i < n; i++){
            int temp = a[i];
            int j = i-1;
            while (j > -1 && a[j] > temp){//必须保证遍历前面所有元素包括第一个
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = temp;
        }
    }
    public static void main(String[] args) {
        int[] a = new int[]{5,4,8,1,0,9};
        new Insertion().sort(a);
        for(int i : a)
            System.out.print(i+" ");
    }
}
